#!/usr/env/bin python
# -*- coding: utf-8 -*-

# @Time    : 2018/11/6 11:45
# @Author  : yangdy
# @Email   : yangdy@egu360.com
# @File    : 中级-零钱兑换.py
# @Software: PyCharm


class Solution:
    def coinChange(self, coins, amount):
        """
        :type coins: List[int]
        :type amount: int
        :rtype: int
        """
        # m = {amount: 0}
        # max = 0
        # coins.sort()
        # for coin in coins:
        #     keys = m.keys()
        #     keys = sorted(keys)
        #     lkeys = len(keys)
        #     print(m)
        #     for i in range(lkeys):
        #         k = keys[i]
        #         v = m[k]
        #         left = k - coin
        #         v += 1
        #         while left >= 0:
        #             if not left in m or m[left] > v:
        #                 m[left] = v
        #             left -= coin
        #             v += 1
        # if 0 in m:
        #     return m[0]
        # else:
        #     return -1

        if amount <= 0:
            return 0
        mm = [0] * (amount + 1)
        for coin in coins:
            for i in range(amount):
                if i == 0 or mm[i]:
                    if i + coin <= amount:
                        if mm[i + coin] <= 0 or mm[i + coin] > mm[i] + 1:
                            mm[i + coin] = mm[i] + 1
        if mm[amount]:
            return mm[amount]
        else:
            return -1


def main():
    solve = Solution()
    coins = [1, 2, 5]
    amount = 11
    coins = [208, 170, 205, 425, 124, 375]
    amount = 7130
    print(coins, amount)
    print(solve.coinChange(coins, amount))


if __name__ == '__main__':
    main()
